<?php
namespace Homework5;

class UnionSet {
	
	private $ids;
	private $sizes;		// union sets' sizes
	private $unionCount;
	private $searchCount;
	private $parentSearchCount;
	private $maze;
	private $size;
	
	public function __construct($size, Maze $maze = null) {
		$this->create($size, $maze);
		$this->unionCount = 0;
		$this->searchCount = 0;
		$this->parentSearchCount = 0;
		$this->size = $size;
	}
	
	private function create($size, Maze $maze = null) {
// 		if ($maze == null) {
// 			$maze = new Maze();
// 		}
// 		$this->maze = $maze;
// 		$this->maze->draw($size);	
// 		$nrElements = count($this->maze->getElements());
		
		$ids = array();
		$sizes = array();
		for ($i = 0; $i < $nrElements; $i++) {
			$ids[$i] = -1;
			$sizes[$i] = 1;
		}
		$this->ids = $ids;
		$this->sizes = $sizes;
	}
	
	public function unionFind($a, $b) {
		if (!$this->find($a, $b)) {
			if (abs($a - $b) == 1 || abs($a-$b) == $this->size) {
				$this->union($a, $b);
			}
		}
	}
	
	public function root($i) {
		if ($this->ids[$i] < 0) {
			return $i;
		} else {
			$this->parentSearchCount++;
			// Path compression, i.e. element i parent is path's root 
			$this->ids[$i] = $this->root($this->ids[$i]);
			
			return $this->ids[$i];
		}
	}
	
	public function find($a, $b) {
		$this->searchCount++;
		
		return $this->root($a) == $this->root($b);
	}
	
	public function union($a, $b) {
		$this->unionCount++;
		
		$rootA = $this->root($a);
		$rootB = $this->root($b);
// 		$this->maze->removeWall($rootA, $rootB);
// 		$this->maze->render();
		$this->update($rootA, $rootB);
	}
	
	public function update($rootA, $rootB) {
		if ($this->sizes[$rootA] < $this->sizes[$rootB]) {
			$this->ids[$rootA] = $rootB;
			$this->sizes[$rootB] += $this->sizes[$rootA];
		} else {
			$this->ids[$rootB] = $rootA;
			$this->sizes[$rootA] += $this->sizes[$rootB];
		}
	}
	
	public function isUnified() {
		
		return (count($this->ids)-1) == $this->unionCount;
	}
	
	public function getIds() {
		
		return $this->ids;
	}
	
	public function getSizes() {
		
		return $this->sizes;
	}
	
	public function getSearchCount() {
		
		return $this->searchCount;
	}
	
	public function getUnionCount() {
		
		return $this->unionCount;
	}
	
	public function getParentSearchCount() {
		
		return $this->parentSearchCount;
	}
	public function getMaze() {
		
		return $this->maze;
	}
}